Query optimization depends in large part on efficient and accurate cardinality estimates of intermediate results and the plan for the order of a sequence or set of operators representative of a query. In some aspects, the order of the operators to implement the query may be determined with relative ease, particularly as compared to the process of accurately determining a cardinality estimate.
Various methods have been previously proposed for determining cardinality estimates. However, a number of the previous proposals may result in unbounded estimation errors. Also, since the building of a histogram typically involves the accessing of data via a data scan the manner in which the data is stored may impact the efficiency of the histogram construction.